The present invention relates generally to routing of data through a communications network, and more specifically to a system and method for calculating deadlock-free sets of paths for passing information over a communication network.
As it is generally known, routing is the process of determining the nodes through which a data unit is forwarded along its path between a source and a destination within a network. The route taken by data, such as a packet or other specific type of data unit, is also referred to herein as the path taken between the source and destination. Routing is performed by various kinds of data forwarding devices, including routers and switches. A forwarding device that performs routing is typically connected to multiple communication links, and operates to select at least one of those communication links as an output link for each received data unit to be forwarded. Thus it is seen that routing in general is concerned with determining which paths are used for forwarding data units through a network.
Traditional routing techniques have attempted to compute paths that do not contain loops. However, even where loop-free paths have been determined, traffic flows can interact with each other to cause a problem known as “deadlock” within the network. For example, deadlock can occur within a group of switches, each of which has buffers full of received data. Each of the switches in such a group may be unable to forward its received data because the switch to which that data must be forwarded has no available buffers to store the data.
FIG. 1 illustrates the occurrence of deadlock in a group of four switches, referred to as nodes, within a communication network. The nodes 10, 14, 18 and 22 of FIG. 1 each include buffers for storing data, and may be interconnected using any conventional type of communication links or media. The data flows 12, 16, 20 and 24 consist of data units passed over such communication links between the nodes 10, 14, 18 and 22.
In the scenario illustrated in FIG. 1, node 10's buffers are filled with packets received from a data flow 12. However, node 10 cannot forward the packets it has received to node 14, since node 14's buffers are filled with packets from a data flow 16 that node 14 can't forward to node 18, since node 18's buffers are filled with packets from data flow 20. Similarly, node 18 cannot forward its data to node 22, since node 22's buffers are also filled. FIG. 1 thus illustrates how the occurrence of deadlock in a network can result in significant network performance problems.
Existing routing systems have been developed which provide deadlock-free sets of paths by either constraining the topology of the network itself, and/or by constraining the routes which may be taken through the network. For example, the topology of a network may be constrained such that the network topology is arranged as a grid. Given a grid topology, if all paths through the network are required to first traverse links horizontally as far as necessary, then vertically to the destination node, the network will be deadlock-free. Also, if the network topology is a tree, which by definition includes no loops, then the network will be deadlock-free during operation.
Existing systems have employed centralized techniques to compute deadlock-free sets of paths. A centralized approach operates such that one node obtains the complete topology of the network, for example by having each other node in the network report which neighbor nodes it is connected to. The central node then calculates a set of deadlock-free paths for the entire network. Once computed, these paths can then be distributed in the form of “forwarding tables” to all other nodes, thus informing each node in the network which neighbor node to forward a received data unit to, for each potential destination within the network.
One existing centralized approach to determining paths through a network is known as “up/down routing.” In up/down routing, one of the nodes in the network is chosen arbitrarily as the root of a spanning tree for the network. All links within the network are then designated as “up” or “down” links with respect to the root node. The determination of an “up” or “down” state for a given link is based on the position of the link with respect to the spanning tree. A link is “up” if it points from a lower to a higher level node in the tree. Otherwise, the link is considered a “down” link. For nodes at the same level, node IDs are used to break the tie. Routing of packets from a source to a destination is performed such that any “up” links (towards the root) in the path are traversed before any “down” links are traversed (away from the root) in order to reach the destination. Accordingly, once a “down” link has been traversed, no “up” links may be used within that path. This approach prevents loops, and thus the routing is deadlock-free.
A significant problem with up/down routing is that links near the root of the spanning tree get congested and become bottlenecks leading to lower throughput. In other words, a disproportionate amount of traffic may be directed through links connected to the root node. Accordingly, it would be desirable to have a centralized system for deadlock-free path determination that provides for a more even distribution of traffic on the network during network operation.